The arithmetic unit is one of the most important components of any integrated electronic data processing system. Arithmetic units perform a wide variety of mathematical functions upon operands which are transmitted from other portions of an integrated system. The basic addition subtraction and multiplication functions are quickly and efficiently performed in arithmetic units today. However, presently available techniques for performing division functions have not been completely satisfactory with respect to efficiency and speed.
A common method of performing division in arithmetic systems presently available is through the use of commonly known SRT procedures. In SRT division, the digits of the quotient are developed serially a certain number of bits at a time using table look-ups or programmable logic arrays (PLA) to logically determine each quotient digit as a function of the leading bits of the partial remainder and divisor. An exact new partial remainder is calculated after each digit so that the process may continue indefinitely. A key disadvantage of SRT division is that because of the limitations of the look-up table size, no more than three or four bits per quotient digit can be calculated in any one step. Thus, the division operation using the SRT system takes many steps or iterations. In effect the time required for SRT division grows linearly with the number of bits of precision, and becomes relatively slower in comparison to certain approximation techniques for higher precision division operations.
A more recently developed system employs a division system using a Newton-Raphson approximation technique. In this system, an approximation of the reciprocal of the divisor is calculated using an iterative process to achieve a value for the reciprocal in a full precision format. The full precision reciprocal approximation is then multiplied by the full precision dividend to achieve an estimate of the full precision quotient. Only a bound on the indeterminate error of the estimated quotient is known and this information is inadequate for implementation of precise rounding. To achieve precise rounding the indeterminacy in the error is removed by a second full precision multiplication. In the second full precision multiplication step, the divisor is multiplied by the estimated quotient and a corresponding remainder is computed. This information is then sufficient to allow for the appropriate IEEE standard rounding procedures. The Newton-Raphson division sequence is superior to the SRT division, but still contains a major disadvantage. The Newton-Raphson division requires two full precision multiplies which are time consuming. The Convergence Division Method, which is effectively a variation of the Newton-Raphson division process, requires similar steps to remove the indeterminacy in the error to effect IEEE standard roundings.
Therefore, a need has arisen for a system which uses a division process which results in an exact result which can be used for appropriate IEEE standard rounding procedures, but which is less time consuming than and more efficient than previously developed systems.